Asynchronous transfer of messages between application programs running on different data processing systems within a network is well known in the art, and is implemented by a number of commercially available message-oriented middleware products. These products include IBM Corporation's MQSeries family of messaging products, which use asynchronous messaging via queues. A sender application program issues a PutMessage command to send a message to a target queue, and MQSeries queue manager programs handle the complexities of transferring the message under transactional control from the sender to the target queue, which may be remotely located across a heterogeneous computer network. The MQSeries queue manager programs implement transactional assured message delivery even when the destination application is not available at the time the message was sent. The target queue is a local input queue for another application program, which retrieves the message from this input queue by issuing a GetMessage command asynchronously from the send operation. The receiver application program then performs its processing on the message, and may generate further messages. MQSeries and IBM are trademarks of International Business Machines Corporation.
IBM Corporation's MQSeries products and messaging and queuing are described in “MQSeries—An Introduction to Messaging and Queuing” which is available from IBM as and by B. Blakeley, H. Harris and J. R. T Lewis in “Messaging and Queuing using the MQI: Concepts and Analysis, Design and Development”, 1995, McGraw-Hill.
A feature of the Message Queuing Interface (MQI) implemented by IBM's MQSeries products is the ability to handle GetMessage requests with a wait option. If the “Get_wait” option is specified by an application and no message is currently available which satisfies a specified criteria, the application will wait to be notified when a message which satisfies the criteria subsequently arrives on the queue.
One known implementation of this feature is to use indexed queues, where indices are maintained to expedite GetMessage operations on the queue. Example index types are:                NONE—No index is maintained        MSGID—An index of message identifiers is maintained. This is used when messages are usually retrieved by message identifier as a selection criteria on the GetMessage call        CORRELID—An index of correlation identifiers is maintained. This is used when messages are usually retrieved by correlation identifier as a selection criteria on the GetMessage call.        
An application putting a message to a queue optionally assigns values to the message identifier and correlation identifier. These key values combined with the index type of the queue dictate which, if any, index entries are built for the message. In a single queue manager environment, the index entries live in the single owning queue manager and the time taken to perform message retrieval in response to a GetMessage request can be decreased by the GetMessage utilising the index associated with the queue. An application issuing a GetMessage request for a message with a specific message identifier or correlation identifier can optionally request to wait until a message which satisfies the criteria arrives on the queue. In a single queue manager environment, the queue manager can easily determine when a message is Put that satisfies an application which issued “Get_wait”.
However, some resource manager products including IBM's MQSeries message queue manager products implement clustering for increased message throughput and availability. This clustering can involve a number of queue manager programs managing retrieval of messages from a shared queue, as well as putting messages to shared queues. In an example messaging solution for a data processing system running IBM Corporation's OS/390 operating system, the shared queues may be stored in OS/390 Coupling Facility list structures. The Coupling Facility may be located on a dedicated system to provide highly available, shared storage which is accessible by one or more programs coupled to the Coupling Facility and performs operations requested by those coupled programs. Data and controls to be shared between the coupled programs are stored in storage structures of the Coupling Facility. These storage structures can include cache, list and lock structures. Aspects of the operation of a Coupling Facility are described in detail in U.S. Pat. Nos. 5,317,739, 5,561,809 and 5,706,432. (OS/390 is a trademark of International Business Machines Corporation).
In a shared queue environment, a number of problems have to be addressed to implement the wait option for GetMessage requests, including how to notify applications which are running on different systems from the shared queue of the arrival of a message on that queue.
A further problem is how to avoid messages being retrieved from a queue before the message Put operation has been committed. A known solution to this problem is to apply locks to each message while the message Put operation is in-doubt, and to only release the lock and make the message available for retrieval by other applications after the Put operation has been committed. In a shared queue environment, managing the application and removal of these locks in response to requests from remote processes is a significant overhead. In particular, if GetMessage requests specify index information such as a message identifier (message ID) or correlation identifier (correlation ID), commit duration locks cannot be applied to the message ID or correlation ID because this would lock committed as well as uncommitted messages which have the same index and a solution which monitors the availability of messages with reference to an index only to discover that the messages are locked would be inefficient.
The use of shared queues in a multi-processor environment is also known from U.S. Pat. No. 5,887,168, for example.
This discloses enqueuing a received message onto a shared queue and then any one of a plurality of systems which has available capacity can retrieve and process the message.
Where appropriate, responses are enqueued onto the shared queue for delivery back to the original sender. A list structure comprised of a plurality of sub-lists is used to implement the queue.